/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core/algorithm
// Copyright( c) 2013.  All Rights Reserved
//
// File:		AEQuickSort.h
// Author:		Gianluca Belardelli
// Date:		04/10/2013
//
/////////////////////////////////////////////////////////////////////////
#ifndef _AEQUICKSORT_H_
#define _AEQUICKSORT_H_

/// Implementazione Quicksort basata su:
/// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
///
/// On average, this quicksort algorithm runs in time proportional to
/// N log N, independent of the input distribution. The algorithm
/// uses Sedgewick's partitioning method which stops on equal keys. 
/// This protects against cases that make many textbook implementations, 
/// even randomized ones, go quadratic (e.g., all keys are the same).
class AEQuickSort : public IAESorter
{
// Methods
private:
	void _quickSort( void *lpArray, int nLeft, int nRight, IAEComparator *lpComparator );
	int _partition( void *lpArray, int nLeft, int nRight, IAEComparator *lpComparator );

public:
	void Sort( void *lpArray, int nCount, IAEComparator *lpComparator );

};

#endif // _AEQUICKSORT_H_